In general, a mesh includes elements, which typically are simple shapes such as tetrahedrons, hexahedrons, prisms, and pyramids. These simple shapes have faces, edges, and vertices. A mesh is simply a collection of these elements and the mathematical description of the relationship between the nodes, edges, faces and the elements. If the vertex of one element lies in the interior of the edge of another element, that vertex is a hanging node. As depicted in FIG. 1, the edge 102 ends at a node 104 in the middle of the edge 106. The node 104 is typically called a hanging node. If an edge of one element is on the face of another element that edge is typically called a hanging edge. The elements of a tetrahedral mesh are tetrahedrons and the mesh can be non-continuous or continuous. In a continuous mesh there are no hanging nodes on edges, there are no hanging edges on tetrahedral faces, the elements do not intersect one another, there are no gaps between the elements, and no element cuts across the surface of any other element.
In numerical analysis of industrial systems or structures, complicated three-dimensional shapes are commonly broken down into, or approximated by, a tetrahedral mesh, in the process of setting up and/or solving equations for finite element analysis, especially in the numerical solution of partial differential equations. Such meshes have wide applications in practical applications in computational fluid dynamics, aerodynamics, electromagnetic fields, civil engineering, chemical engineering, naval architecture and engineering, and related fields. Tetrahedral meshes that are continuous, i.e., the tetrahedrons forming the mesh do not intersect or overlap with each other, can be particularly beneficial in the analysis and/or design of various physical systems and structures such as printed circuit boards, integrated circuits, cable systems including optical fiber communication systems, and bundled cable systems used in vehicles, conduit systems used in the oil and gas industry, silicon and other substrates, redistribution layers, electronic packages, and microwave devices, because continuous mesh based analysis/design is often more efficient. For example, relative to using other analysis techniques, using a continuous mesh can decrease the analysis/design time, resources requirements in terms of the number of processors, memory size, etc.
Meshes can represent prismatic objects. A prism is typically a polyhedron created by taking a polygon and sweeping it along a vector. If the vector is perpendicular to the polygon the resulting prism is called a right prism, such as the hexagonal prisms 202 depicted in FIG. 2A. If the vector is not perpendicular to the polygon, the resulting prism is called an oblique prism. The polygon being swept usually does not include holes, and is usually convex.
With reference to FIG. 2B, an extrusion is similar to a prism, but the cross section being swept may include holes. Alternatively or in addition, the cross section may be concave. The objects obtained by sweeping polygons having holes and/or other concavities are prismatic, but they are typically not called prisms; instead, they are commonly called extrusions. The prismatic objects 204 have holes and the prismatic object 206 has both a hole and a concavity. The extrusions, i.e., prismatic objects 204, 206 are swept in a Z direction through a short distance relative to the dimensions of these objects in the X-Y cross-sectional plane. The prisms 202 are swept through a relatively longer distance in the Z direction. In general, however, any particular relationship between the dimensions in X, Y, and Z directions is not required. Prismatic objects including prisms and extrusions may have any dimensions in the X-Y cross-sectional plane and in the Z direction.
In general, a volumetric object is an object that encloses a volume, and can be a solid, a liquid, a gas, or a combination any two or all three. A sheet object generally has an area, but lacks any substantial thickness or volume, and a wire object generally has a length, but lacks any substantial area and volume. Cartesian non boundary conformal meshing methods for generating meshes of volumetric objects generally divide space along the coordinate axes into octants/quadrants, recursively divide the octants/quadrants that cut the volumetric objects to be meshed, and usually create a hexahedral non-boundary conformal mesh. Insert-point-and-swap methods typically create a convex hull that contains all of the volumetric objects to be meshed, then insert vertices one by one into the mesh until all vertices of the volumetric objects are in the mesh. All elements cutting through object surfaces are cut repeatedly, until no element cuts across any surface of any object. Volume Decomposition methods divide the space with a large number of elements of desired shape, and recursively subdivide all elements that cut across object surfaces, and terminate after a specified number of levels or when the element size is not larger than a specified threshold. The vertices of the elements are then adjusted to prevent them from crossing surfaces.
These generic methods can be very slow, often taking hours to generate a continuous mesh representing a complex structure. In some instances, these techniques are simply unable to generate a mesh for a specified structure. Improved methods and systems for generating continuous meshes representing volumetric objects are therefore needed.